10.7. Kümeleme Sıralaması (Heap Sort)

Kümeleme sıralamasının temeli ikili kümeleme ağacı (binary heap tree) kurulmasına dayanır. Sıralanacak elemanlar ile önce bir kümeleme ağacı oluşturulur; bu durumda kök en büyük değere sahiptir. Daha sonra sıralı diziyi elde etmenin iki yolu vardır; birisi, bir başka dizi gerektirmeksizin sırasız elemanların bulunduğu dizi üzerinde çalışır, diğeri sıralı elemanların tutulacağı yeni bir dizi gerektirir.

Kümeleme sıralamasının kaba-kodu (pseudo code) yukarıdaki gibi verilebilir; görüldüğü gibi önce sıralanacak elemanlardan bir kümeleme ağacı oluşturulmakta ve ardından çevrim sayacı k olan bir for döngüsü kurulmuştur. Çevrim sayacı k'nın başlangıç değeri A'nın eleman sayısı, veya başka bir deyişle ağaçtaki düğüm sayı n'dir; bu, elemanSayısı(A) ile öğrenilir. C dilinde dizi indisleri sıfırdan başladığı için bu değerden bir çıkarılır ve k ilk çevrimde dizinin son elemanı olan (n-1)'i gösterir. Çevrim k>1 olduğu sürece sürer; bu, dizinin ilk iki elemanına kadar devam eder anlamındadır. Döngü içerisinde yapılanlar ise kümeleme ağacının kökü kok adlı değişkene alınır ve dizinin k. elemanı (bu eleman ağacın en sağdaki yaprak düğümüdür) ile yer değiştirilir. Daha sonra Ağaç kök çıkarılmış olarak yeniden kümelenir; yani kümeleme ağacı özelliği yeniden sağlanır. Döngü sonlandığında A dizisi sıralanmış hale gelir.

! Kümeleme sıralamasının davranışının adımlarını görmek için Devam düğmesine tıklayınız.